/**
 * Initialize your data structure here.
 * @author dingyue.zhf
 * @description 981. 基于时间的键值存储 https://leetcode-cn.com/problems/time-based-key-value-store/ 位运算
 *
 * 关键条件 返回先前调用 set(key, value, timestamp_prev) 所存储的值，其中 timestamp_prev <= timestamp 。
 *
 * timestamp是递增的
 */
var TimeMap = function () {
  this.map = new Map();
};

/**
 * @param {string} key
 * @param {string} value
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function (key, value, timestamp) {
  // 取离timestamp最近的时间戳
  if (!this.map.has(key)) {
    this.map.set(key, [[value, timestamp]]);
    return this.map;
  }
  const arr = this.map.get(key);
  arr.push([value, timestamp]);
  return this.map;
};

/**
 * @param {string} key
 * @param {number} timestamp
 * @return {string}
 * @description 二分查找+map
 */
TimeMap.prototype.get = function (key, timestamp) {
  const arr = this.map.get(key);
  if (!arr) {
    return '';
  }
  let l = 0,
    r = arr.length - 1,
    m;
  // 二分法需要勤加练习
  // 注意二分查找成立条件是小于还是小于等于
  // l = r是什么情况？
  // 取小于timestamp最大的时间戳
  // 二分查找还是不熟
  // 二分查找为什么能查单个数
  // 中位数是0
  // 这里查找的结果是不超过timestamp的最大值
  // 这里二分查找的结果是
  while (l <= r) {
    m = (l + r) >> 1;
    if (arr[m][1] < timestamp) {
      l = m + 1;
    } else if (arr[m][1] > timestamp) {
      r = m - 1;
    } else {
      return arr[m][0];
    }
  }
  // r小于0表示数组长度为空
  return r >= 0 ? arr[r][0] : '';
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */
